#pragma once
#include<vector>
using namespace std;
template<size_t N>
class BitSet
{
public:
	BitSet()
	{
		_bs.resize(N / 32 + 1);
	}
	void set(size_t x)
	{
		int i = x / 32;
		int y = x % 32;
		_bs[i] |= (1 << y);
	}
	void reset(size_t x)
	{
		int i = x / 32;
		int y = x % 32;
		_bs[i] &= (~(1 << y));
	}
	bool test(size_t x)
	{
		int i = x / 32;
		int y = x % 32;
		return _bs[i] & (1 << y);
	}
private:
	vector<int> _bs;
};
template<size_t N>
class Two_BitSet
{
public:
	void set(size_t x)
	{
		bool bit1 = _bs1.test(x);
		bool bit2 = _bs2.test(x);
		if (!bit1 && !bit2)
		{
			_bs2.set(x);
		}
		else if (!bit1 && bit2)
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
		else
		{
			_bs2.set(x);
		}
	}
	int GetCount(size_t x)
	{
		bool bit1 = _bs1.test(x);
		bool bit2 = _bs2.test(x);
		if (!bit1 && !bit2)
		{
			return 0;
		}
		else if (!bit1 && bit2)
		{
			return 1;
		}
		else if (bit1 && !bit2)
		{
			return 2;
		}
		else
			return 3;
	}
private:
	BitSet<N> _bs1;
	BitSet<N> _bs2;
};

void Test_TwoBitSet()
{
	int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };
	int sum = 0;
	Two_BitSet<100> bs;
	for (auto x : a)
		bs.set(x);
	for (int i = 0; i < 100; i++)
	{
		cout << bs.GetCount(i) << " ";
	}
	cout << endl;

}

void Test_BitSet()
{
	int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
	int a2[] = { 5,3,5,99,6,99,33,66 };

	BitSet<100> bs;
	for (auto e : a1)
	bs.set(e);
	for (auto e : a2)
		cout << bs.test(e) << " ";
	cout << endl;
}
